package leetcode.weekly.week328;

//Solution2Test
public class Solution2 {

	public int[][] rangeAddQueries(int n, int[][] queries) {
		int[][] ans = new int[n][n];
		int m = queries.length;
		for (int i = 0; i < m; i++) {
			int[] cur = queries[i];
			int r1 = cur[0], c1 = cur[1], r2 = cur[2], c2 = cur[3];
			ans[r1][c1] += 1;
			if (c2 + 1 < n)
				ans[r1][c2 + 1] -= 1;
			if (r2 + 1 < n)
				ans[r2 + 1][c1] -= 1;
			if (c2 + 1 < n && r2 + 1 < n)
				ans[r2 + 1][c2 + 1] += 1;
		}
		for (int j = 0; j < n; j++) {
			int sum = ans[0][j];
			for (int i = 1; i < n; i++) {
				sum += ans[i][j];
				ans[i][j] = sum;
			}
		}
		for (int i = 0; i < n; i++) {
			int sum = ans[i][0];
			for (int j = 1; j < n; j++) {
				sum += ans[i][j];
				ans[i][j] = sum;
			}
		}
		return ans;
	}

}
